/*
题目: 最多可以参加的会议数目
给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。

请你返回你可以参加的 最大 会议数目。

https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended
 */
public class MaxEvents {
    // 贪心 + 堆优化
    public int maxEvents(int[][] events) {
        // 按照出场时间
        Arrays.sort(events, (int[] o1, int[] o2) -> {return o1[0] - o2[0];});
        int curDay = events[0][0], n = events.length; // 最早会议的开始时间

        // 按照结束时间形成小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<> ();
        // 所有会议的结束时间入堆
        // 每天只能执行一个会议, 所以当前天数 < 某个会议的结束时间, 这个会议就没法安排
        int src = 0;
        int pos = 0; // 用于遍历events数组

        while (pos < n || !heap.isEmpty()) {
            // 开始时间轮到后再将结束时间入堆
            while (pos < n && events[pos][0] <= curDay) {
                heap.offer(events[pos++][1]);
            }

            // 早结束的先执行
            while (!heap.isEmpty() && heap.peek() < curDay) {
                heap.poll();
            }

            if (!heap.isEmpty()) {
                heap.poll();
                src ++;
            }
            curDay ++;  // 开始时间还太早就需要 ++
        }

        return src;
    }

    // 贪心 超时
    public int maxEvents(int[][] events) {
        // 最早结束的最先选择
        Arrays.sort(events, new Comparator<int[]> () {
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        Set<Integer> set = new HashSet<> ();
        for (int[] elem : events) {
            for (int i = elem[0]; i <= elem[1]; i++) {
                if (set.add(i)) {
                    break;
                }
            }
        }

        return set.size();
    }
}
